|
Mathematical induction is a mathematical proof technique, most commonly used to establish a given statement for all natural numbers, although it can be used to prove statements about any well-ordered set. It is a form of direct proof, and it is done in two steps. The first step, known as the base case, is to prove the given statement for the first natural number. The second step, known as the inductive step, is to prove that the given statement for any one natural number implies the given statement for the next natural number. From these two steps, mathematical induction is the rule from which we infer that the given statement is established for all natural numbers. The method can be extended to prove statements about more general well-founded structures, such as trees; this generalization, known as structural induction, is used in mathematical logic and computer science. Mathematical induction in this extended sense is closely related to recursion. Mathematical induction, in some form, is the foundation of all correctness proofs for computer programs.〔 〕 Although its name may suggest otherwise, mathematical induction should not be misconstrued as a form of inductive reasoning (also see Problem of induction). Mathematical induction is an inference rule used in proofs. In mathematics, proofs including those using mathematical induction are examples of deductive reasoning, and inductive reasoning is excluded from proofs. ==History== In 370 BC, Plato's Parmenides may have contained an early example of an implicit inductive proof.〔(Mathematical Induction: The Basis Step of Verification and Validation in a Modeling and Simulation Course )〕 The earliest implicit traces of mathematical induction can be found in Euclid's〔(【引用サイトリンク】title=Euclid's Proof of the Infinitude of Primes (c. 300 BC) )〕〔(【引用サイトリンク】title=Euclid's Primes )〕〔(【引用サイトリンク】title=Proofs of the Infinity of the Prime Numbers )〕 proof that the number of primes is infinite and in Bhaskara's "cyclic method". An opposite iterated technique, counting ''down'' rather than up, is found in the Sorites paradox, where one argued that if 1,000,000 grains of sand formed a heap, and removing one grain from a heap left it a heap, then a single grain of sand (or even no grains) forms a heap. An implicit proof by mathematical induction for arithmetic sequences was introduced in the ''al-Fakhri'' written by al-Karaji around 1000 AD, who used it to prove the binomial theorem and properties of Pascal's triangle. None of these ancient mathematicians, however, explicitly stated the inductive hypothesis. Another similar case (contrary to what Vacca has written, as Freudenthal carefully showed) was that of Francesco Maurolico in his ''Arithmeticorum libri duo'' (1575), who used the technique to prove that the sum of the first ''n'' odd integers is ''n''2. The first explicit formulation of the principle of induction was given by Pascal in his ''Traité du triangle arithmétique'' (1665). Another Frenchman, Fermat, made ample use of a related principle, indirect proof by infinite descent. The inductive hypothesis was also employed by the Swiss Jakob Bernoulli, and from then on it became more or less well known. The modern rigorous and systematic treatment of the principle came only in the 19th century, with George Boole,〔"It is sometimes required to prove a theorem which shall be true whenever a certain quantity ''n'' which it involves shall be an integer or whole number and the method of proof is usually of the following kind. ''1st''. The theorem is proved to be true when ''n'' = 1. ''2ndly''. It is proved that if the theorem is true when ''n'' is a given whole number, it will be true if ''n'' is the next greater integer. Hence the theorem is true universally. . .. This species of argument may be termed a continued ''sorites''" (Boole circa 1849 ''Elementary Treatise on Logic not mathematical'' pages 40–41 reprinted in Grattan-Guinness, Ivor and Bornet, Gérard (1997), ''George Boole: Selected Manuscripts on Logic and its Philosophy'', Birkhäuser Verlag, Berlin, ISBN 3-7643-5456-9)〕 Augustus de Morgan, Charles Sanders Peirce,〔 Reprinted (CP 3.252-88), (W 4:299-309).〕 Giuseppe Peano, and Richard Dedekind.〔 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Mathematical induction」の詳細全文を読む スポンサード リンク
|